import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//根据前序和中序遍历序列来创建二叉树 力扣105
class Solution7 {
    int preorder[];
    int inorder[];
    int pre_idx;
    Map<Integer,Integer> map_idx = new HashMap<Integer,Integer>();
    public TreeNode helper(int left,int right){
        if(left>right){
            return null;
        }
        int root_val = preorder[pre_idx];
        TreeNode root = new TreeNode(root_val);
        int index = map_idx.get(root_val);
        pre_idx++;
        root.left = helper(left,index-1);
        root.right = helper(index+1,right);
        return root;

    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int idx = 0;
        int pre_idx = 0;
        for(Integer val:inorder){
            map_idx.put(val,idx++);
        }
        return helper(0,inorder.length-1);

    }
}